/*************************************************************************
    > File Name:    list_node.h
    > Author:       陈猛
    > Mail:         chen-meng@example.com
    > Created Time: 2019年09月12日 星期四 16时27分13秒
    > Description:  一个基于链表的容器
 ************************************************************************/

#ifndef _LIST_NODE_H_
#define _LIST_NODE_H_

/** @note 一个循环列表
 * 不同的列表可以继承它, 顺时针方向添加，看作队尾，数据都用root.add添加到队尾
 *
 *      -----数据插入方向---->>>
 * |----------------------------------|
 * | root | item1 | ... | ...  | item |
 * |  ... |--------------------| ...  |
 * | itemn|                    |      |
 * |      |                    | item |
 * |      |------------ -------|      |
 * |    <<<-----流动方向------         |
 * |----------------------------------|
**/
class ListNode
{
public:
    ListNode()
        : next(this), prev(this)
    {}

    /** FIFO  add at last
     * -------------------
     * |   | this | item |
     * -------------------
    */
    inline void add(ListNode *item)
    {
        item->next = this->next;
        item->prev = this;
        this->next->prev = item;
        this->next = item;
    }

    /** FIFO  add at first
     * --------------------
     * | item | this |    |
     * --------------------
    */
    inline void addFirst(ListNode *item)
    {
        item->next = this;
        item->prev = this->prev;

        this->prev->next = item;
        this->prev = item;
    }

    /** first
     * --------------------
     * | prev | this |    |
     * --------------------
    */
    inline ListNode *getFirst()
    {
        return this->prev;
    }

    /** last
     * --------------------
     * |    | this | next |
     * --------------------
    */
    inline ListNode *getLast()
    {
        return this->next;
    }

    inline void del()
    {
        if (next == this
                || prev == this)
        {
            return;
        }
        next->prev = prev;
        prev->next = next;
        next = this;
        prev = this;
    }

    inline bool isEmpty() const
    {
        return this->next == this;
    }

    inline int length() const
    {
        ListNode *item;
        int count = 0;
        for(item = this->next; item != this; item = item->next)
        {
            ++count;
        }
        return count;
    }

    // 把first 和last 这条链，加到this
    void _M_transfer(ListNode * const __first, ListNode * const __last)
    {
        if (this != __last)
        {
            // Remove [first, last) from its old position.
            __last->prev->next  = this;
            __first->prev->next = __last;
            this->prev->next    = __first;

            // Splice [first, last) into its new position.
            ListNode* const __tmp = this->prev;
            this->prev                = __last->prev;
            __last->prev              = __first->prev;
            __first->prev             = __tmp;
        }
    }

    // stl 中的列表互相交换
    void  swap(ListNode& __x, ListNode& __y)
    {
        if ( __x.next != &__x )
        {
            if ( __y.next != &__y )
            {
                // Both __x and __y are not empty.
                __swap(__x.next, __y.next);
                __swap(__x.prev, __y.prev);
                __x.next->prev = __x.prev->next = &__x;
                __y.next->prev = __y.prev->next = &__y;
            } else
            {
                // __x is not empty, __y is empty.
                __y.next = __x.next;
                __y.prev = __x.prev;
                __y.next->prev = __y.prev->next = &__y;
                __x.next = __x.prev = &__x;
            }
        } else if ( __y.next != &__y )
        {
            // __x is empty, __y is not empty.
            __x.next = __y.next;
            __x.prev = __y.prev;
            __x.next->prev = __x.prev->next = &__x;
            __y.next = __y.prev = &__y;
        }
    }

    void _M_reverse()
    {
        ListNode* __tmp = this;
        do
        {
            __swap(__tmp->next, __tmp->prev);

            // Old next node is now prev.
            __tmp = __tmp->prev;
        }
        while (__tmp != this);
    }

    // stl中的挂钩，把当前this节点，添加到__position前面**
    // 与add功能相同，设计想法相左，传入的参数才是新节点，this才是position
    void _M_hook(ListNode* const __position)
    {
        this->next = __position;
        this->prev = __position->prev;
        __position->prev->next = this;
        __position->prev = this;
    }
    // std中脱钩
    // 与del功能相同
    void _M_unhook()
    {
        ListNode* const __next_node = this->next;
        ListNode* const __prev_node = this->prev;
        __prev_node->next = __next_node;
        __next_node->prev = __prev_node;
    }

    ListNode *next;
    ListNode *prev;

private:
    void __swap(ListNode *__x, ListNode *__y)
    {
        ListNode *tmp = __x;
        __x = __y;
        __y = tmp;
    }
};

/** 从队列的的尾部开始遍历 */
#define TRAVEL_LIST(root) \
    for(ListNode *tmp = root.next; tmp != &root; tmp = tmp->next)

/** 从队列的的尾部开始遍历, 可以删除tmp节点 */
#define TRAVEL_LIST_AND_DEL(root) \
    for(ListNode *tmp = root.next, *next = tmp->next; \
        tmp != &root; \
        tmp = next, next = next->next)

/** 从对列的头部进行遍历 */
#define TRAVEL_LIST_BACK(root) \
    for(ListNode *tmp = root.prev; tmp != &root; tmp = tmp->prev)

/** 从对列的头部进行遍历, 可以删除tmp节点 */
#define TRAVEL_LIST_BACK_AND_DEL(root) \
    for(ListNode *tmp = root.prev, *prev = tmp->prev; \
        tmp != &root; \
        tmp = prev, prev = prev->prev)

// 基本项"_Type", 必须继承于ListNode，并且ListNode必须是第一位继承的位置，
// 例如：他跟QObject同时被继承，绝对会出现异常或段错误，因为操作了非法内存
// 这种写法，类似上面的写法，只是使用C++的风格封装了一下
// 同时他优于ListTable类的写法，减少了push一项数据，需要重新new一次ListNode的弊端
// 最近发现好像没有上面所说的优势，它完全相同于ListTable类，并比ListTable类更繁琐了一些，应该删除
template<typename _Type>
class NodeListTable
{
public:
    class _List_iterator;
    typedef _List_iterator iterator;

    class _List_iterator
    {
    public:
        typedef _List_iterator _Self;
        typedef _Type          value_type;
        typedef _Type*         pointer;
        typedef _Type&         reference;

        _List_iterator()
            : _M_node() {}
        _List_iterator(value_type *n)
            : _M_node(n) {}

        reference operator*() const
        {
            return _M_node;
        }

        pointer operator->() const
        {
            return _M_node;
        }

        _Self& operator++()
        {
            _M_node = static_cast<value_type *>(_M_node->getFirst());
            return *this;
        }

        _Self operator++(int)
        {
            _Self __tmp = *this;
            _M_node = static_cast<value_type *>(_M_node->getFirst());
            return __tmp;
        }

        _Self& operator--()
        {
            _M_node = static_cast<value_type *>(_M_node->getLast());
            return *this;
        }

        _Self operator--(int)
        {
            _Self __tmp = *this;
            _M_node = static_cast<value_type *>(_M_node->getLast());
            return __tmp;
        }

        bool operator==(const _Self& __x) const
        {
            return _M_node == __x._M_node;
        }

        bool operator!=(const _Self& __x) const
        {
            return _M_node != __x._M_node;
        }

        value_type *_M_node;
    };

    void push_back(_Type *it)
    {
        mRoot.add(it);
    }
    void pust_front(_Type *it)
    {
        mRoot.addFirst(it);
    }
    void push_back(iterator it)
    {
        mRoot.add(it._M_node);
    }
    void pust_front(iterator it)
    {
        mRoot.addFirst(it._M_node);
    }

    iterator pop_front()
    {
        if (mRoot.isEmpty())
        {
            return end();
        }
        _Type *node = static_cast<_Type *>(mRoot.getFirst());

        node->del();

        return iterator(node);;
    }
    iterator pop_back()
    {
        if (mRoot.isEmpty())
        {
            return nullptr;
        }
        _Type *node = static_cast<_Type *>(mRoot.getLast());

        node->del();

        return iterator(node);
    }

    iterator begin()
    {
        return iterator(static_cast<_Type *>(mRoot.getFirst()));
    }
    iterator end()
    {
        return iterator(static_cast<_Type *>(&mRoot));
    }
    void remove(iterator it)
    {
        it._M_node->del();
        delete it._M_node;
    }

    template<typename _del>
    void removeAll(_del del)
    {
        if(del)
        {
            TRAVEL_LIST_AND_DEL(mRoot)
            {
                tmp->del();
                del(static_cast<_Type *> (tmp)->_M_data);
                delete static_cast<_Type *> (tmp);
            }
        } else
        {
            clear();
        }
    }

    void clear()
    {
        TRAVEL_LIST_AND_DEL(mRoot)
        {
            tmp->del();
            delete static_cast<_Type *> (tmp);
        }
    }
    bool empty()
    {
        return mRoot.isEmpty();
    }
    int size()
    {
        return mRoot.length();
    }

private:
    ListNode mRoot;
};

#endif // _LIST_NODE_H_
